﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace demo
{
    public static class SortHelper<T> where T : IComparable
    {
        public static void BubbleSort(T[] array)
        {
            int length = array.Length;
            for (int i = 0; i <= length - 1; i++)
            {
                for (int j = length - 1; j >= 1; j--)
                {
                    // 对两个元素进行交换
                    if (array[j].CompareTo(array[j - 1]) < 0)
                    {
                        T temp = array[j];
                        array[j] = array[j - 1];
                        array[j - 1] = temp;
                    }
                }
            }
        }
        

        public static void QuickSort(int[] array, int low, int high)
        {
            if (low < high)
            {
                int index = Partition(array, low, high);
                QuickSort(array, low, index - 1);
                QuickSort(array, index + 1, high);
            }
        }

        public static int Partition(int[] array, int low, int high)
        {
            int i = low,
                j = high;
            // 确定第一个元素作为"基准值"
            int temp = array[i];

            while (i < j)
            {
                // Stage1:从右向左扫描直到找到比基准值小的元素
                while (i < j && array[j].CompareTo(temp) >= 0)
                {
                    j--;
                }
                // 将比基准值小的元素移动到基准值的左端
                array[i] = array[j];

                // Stage2:从左向右扫描直到找到比基准值大的元素
                while (i < j && array[i].CompareTo(temp) <= 0)
                {
                    i++;
                }
                // 将比基准值大的元素移动到基准值的右端
                array[j] = array[i];
            }

            // 记录归位
            array[i] = temp;

            return i;
        }
    }
}
